using Nito.Collections;
using SharpGraphT.Graph;
using SharpGraphT.Sharp.Sharp.Util;

namespace SharpGraphT.Alg.Connectivity;

public class BiconnectivityInspector<TV, TE> where TE : class, new() {
    public BiconnectivityInspector(IGraph<TV, TE> graph) {
        _graph = Objects.RequireNonNull(graph);
        if (graph.Type.IsDirected) {
            graph = new AsUnmodifiableGraph<TV, TE>(graph);
        }
    }

    private IGraph<TV, TE> _graph;

    private HashSet<IGraph<TV, TE>> _blocks;

    private HashSet<TV> _cutpoints;

    private HashSet<TE> _bridges;

    private ISet<TV> _connectedSet;

    private ISet<ISet<TV>> _connectedSets;

    private HashSet<IGraph<TV, TE>> _connectedComponents;

    private IDictionary<TV, IReadOnlySet<IGraph<TV, TE>>> _vertex2Blocks;

    private IDictionary<TV, IGraph<TV, TE>> _vertex2Components;

    private int _time;

    private Deque<TE> _stack;

    private IDictionary<TV, int> _discTime = new Dictionary<TV, int>();

    public IReadOnlySet<TV> GetPoints() {
        PerformLazyInspection();
        return _cutpoints;
    }

    public IReadOnlySet<TE> GetBridges() {
        PerformLazyInspection();
        return _bridges;
    }

    public IReadOnlySet<IGraph<TV, TE>> GetBlocks(TV vertex) {
        Objects.Assert(_graph.ContainsVertex(vertex));

        if (_vertex2Blocks != null) {
            return _vertex2Blocks[vertex];
        }

        _vertex2Blocks = new Dictionary<TV, IReadOnlySet<IGraph<TV, TE>>>();
        foreach (var v in _graph.VertexSet) {
            _vertex2Blocks[v] = new HashSet<IGraph<TV, TE>>();
        }

        foreach (var block in GetBlocks()) {
            foreach (var v in block.VertexSet) {
                ((HashSet<IGraph<TV, TE>>)_vertex2Blocks[v]).Add(block);
            }
        }

        return _vertex2Blocks[vertex];
    }

    public IReadOnlySet<IGraph<TV, TE>> GetBlocks() {
        PerformLazyInspection();
        return _blocks;
    }

    public IReadOnlySet<IGraph<TV, TE>> GetConnectedComponents() {
        if (_connectedComponents != null) {
            return _connectedComponents;
        }

        PerformLazyInspection();
        _connectedComponents = new HashSet<IGraph<TV, TE>>();
        foreach (var vertexComponent in _connectedSets) {
            _connectedComponents.Add(
                new AsSubgraph<TV, TE>(_graph, vertexComponent));
        }

        return _connectedComponents;
    }

    public IGraph<TV, TE> GetConnectedComponent(TV vertex) {
        Objects.Assert(_graph.ContainsVertex(vertex));
        if (_vertex2Components != null) {
            return _vertex2Components[vertex];
        }

        _vertex2Components = new Dictionary<TV, IGraph<TV, TE>>();
        foreach (var component in GetConnectedComponents()) {
            foreach (var v in component.VertexSet) {
                _vertex2Components[v] = component;
            }
        }

        return _vertex2Components[vertex];
    }

    public bool IsBiconnected() {
        PerformLazyInspection();
        return _graph.VertexSet.Count >= 2 && _blocks.Count == 1;
    }

    public bool IsConnected() {
        PerformLazyInspection();
        return _connectedSets.Count == 1;
    }

    private void Init() {
        _blocks = new HashSet<IGraph<TV, TE>>();
        _cutpoints = new HashSet<TV>();
        _bridges = new HashSet<TE>();
        _connectedSets = new HashSet<ISet<TV>>();
        _stack = new Deque<TE>(_graph.EdgeSet.Count);
        foreach (var v in _graph.VertexSet) {
            _discTime[v] = -1;
        }
    }

    private void PerformLazyInspection() {
        if (_blocks != null) {
            return;
        }

        Init();
        foreach (var v in _graph.VertexSet) {
            if (_discTime[v] == -1) {
                _connectedSet = new HashSet<TV>();
                // TODO Dfs()
            }
        }
    }

    private void BuildBlock(int discTimeCutpoint) {
        var vertexComponent = new HashSet<TV>();

        while (_stack.Any()) {
            var edge = _stack[0];
            var source = _graph.GetEdgeSource(edge);
            var target = _graph.GetEdgeTarget(edge);

            if (_discTime[source] < discTimeCutpoint &&
                _discTime[target] < discTimeCutpoint) {
                break;
            }

            _stack.RemoveFromFront();
            vertexComponent.Add(source);
            vertexComponent.Add(target);
        }

        _blocks.Add(new AsSubgraph<TV, TE>(_graph, vertexComponent));
    }

    private int Dfs(TV v, TV parent) {
        var lowV = ++_time;
        _discTime[v] = _time;
        _connectedSet.Add(v);
        var children = 0;

        foreach (var edge in _graph.EdgesOf(v)) {
            var nv = _graph.GetOppositeVertex(edge, v);
            if (_discTime[nv] == -1) {
                children++;

                _stack.AddToFront(edge);

                var lowNV = Dfs(nv, v);
                lowV = Math.Min(lowNV, lowV);

                if (lowNV > _discTime[v]) {
                    _bridges.Add(edge);
                }

                if (!Objects.IsDefault(parent) && lowNV >= _discTime[v] ||
                    Objects.IsDefault(parent) && children > 1) {
                    _cutpoints.Add(v);
                    BuildBlock(_discTime[nv]);
                }
            } // TODO else
        }

        // TODO
        throw new NotImplementedException();
    }
}